template<class k>
struct SBTNode
{
	k _key;
	SBTNode<k>* _left;
	SBTNode<k>* _right;

	SBTNode(const k& key)
		: _key(key)
		,_left(nullptr)
		, _right(nullptr)
	{
	}
};  

template<class k>
class SBTree
{
	using Node = SBTNode<k>; 
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node<k>;
			return true;
		}

		Node* parent = nullptr;
		Node * cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}
	
	
};